//
// Created by Administrator on 2021/4/6.
//
/*
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：
二叉树：[3,9,20,null,null,15,7],

3
/ \
  9  20
/  \
   15   7
返回其层序遍历结果：

[
[3],
[9,20],
[15,7]
]

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xefh1i/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/
#include <vector>
#include <iostream>
#include <queue>

using namespace std;

//  Definition for a binary tree node.
// 树节点定义
struct TreeNode {
    int val; // 节点值
    TreeNode *left; // 左子节点
    TreeNode *right; // 右子节点

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    explicit TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode *root) { // 层次遍历

        auto nextLevel = queue<TreeNode *>(); // 下一层的节点
        nextLevel.push(root); //放入初始节点
        vector<vector<int>> ans; // 结果
        if (root == nullptr)
            return ans;
        vector<int> temp; // 每一层的结果
        while (not nextLevel.empty()) {
            int n = (int)nextLevel.size();
            for (int i = 0; i < n; i++) {
                TreeNode *t = nextLevel.front(); // 队首
                nextLevel.pop();
                temp.push_back(t->val); // 存值
                if (t->left != nullptr) {
                    nextLevel.push(t->left);
                }
                if (t->right != nullptr)
                    nextLevel.push(t->right);
            }
            ans.push_back(temp);
            temp = {};
        }
        return ans;
    }
};

class Solution2 {
public:
    vector<vector<int>> levelOrder(TreeNode *root) { // 题解
        vector<vector<int>> ret;
        if (!root) {
            return ret;
        }
        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty()) {
            int currentLevelSize = (int)q.size();
            ret.emplace_back();
            for (int i = 1; i <= currentLevelSize; ++i) {
                auto node = q.front();
                q.pop();
                ret.back().push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        return ret;
    }
};

int main() {
//    [3,9,20,null,null,15,7]
    auto t5 = TreeNode(7);
    auto t4 = TreeNode(15);
    auto t3 = TreeNode(20, &t4, &t5);
    auto t2 = TreeNode(9);
    auto t1 = TreeNode(3, &t2, &t3);


    auto sol = Solution2();
    vector<vector<int>> ans = sol.levelOrder(&t1);
    for (auto &an : ans) {
        for (int j : an) {
            cout << j << endl;
        }
    }
    return 0;
}
